require Bitwise
defmodule Letcodir do

	# singleNumbers
	# 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
	def singleNumbers(nums,result \\ nil)
	def singleNumbers(nums,result) when not is_list(result),do: Enum.sort(nums) |> singleNumbers([])
	def singleNumbers(_nums,result) when :erlang.length(result) == 2,do: result
	def singleNumbers(nums,result) do
		[head|tail] = nums
		if :erlang.length(tail) < 1 do
			result ++ [head]
		else
			[first|last] = tail
			if head == first do
				singleNumbers(last,result)
			else
				singleNumbers(tail,result ++ [head])
			end
		end
	end

	# findInMountainArray
	# 给你一个 山脉数组 mountainArr，请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 index 值。
	# 如果不存在这样的下标 index，就请返回 -1。
	# 何为山脉数组？如果数组 A 是一个山脉数组的话，那它满足如下条件：
	# 首先，A.length >= 3
	# 其次，在 0 < i < A.length - 1 条件下，存在 i 使得：
		# A[0] < A[1] < ... A[i-1] < A[i]
		# A[i] > A[i+1] > ... > A[A.length - 1]
	# 你不能直接访问该山脉函数，必须通过MountainArray模组中的函数来获取数据：
		# MountainArray.get(ary,k) - 会返回ary数组中索引为k 的元素（下标从 0 开始）
		# MountainArray.length(ary) - 会返回ary数组的长度
	# 对MountainArray.get的调用不能超过100次
	def findInMountainArray(ary,target) when is_list(ary) do
		fun = fn left,right,fun ->
			if left < right do
				middle = Bitwise.bsr(left + right + 1,1)
				if MountainArray.get(ary,middle) > MountainArray.get(ary,middle - 1) do
					fun.(middle,right,fun)
				else
					fun.(left,middle-1,fun)
				end
			else
				[left,right]
			end
		end
		length = MountainArray.length(ary)
		left = fun.(0,length-1,fun) |> Enum.fetch!(0)
		middle = left
		fun = fn left,right,fun ->
			if left < right do
				middle = Bitwise.bsr(left + right,1)
				if MountainArray.get(ary,middle) >= target do
					fun.(left,middle,fun)
				else
					fun.(middle + 1,right,fun)
				end
			else
				[left,right]
			end
		end
		left = fun.(0,middle,fun) |> Enum.fetch!(0)
		if MountainArray.get(ary,left) == target do
			left
		else
			fun = fn left,right,fun ->
				if left < right do
					middle = Bitwise.bsr(left + right,1)
					if MountainArray.get(ary,middle) <= target do
						fun.(left,middle,fun)
					else
						fun.(middle+1,right,fun)
					end
				else
					[left,right]
				end
			end
			left = fun.(middle,length-1,fun) |> Enum.fetch!(0)
			if MountainArray.get(ary,left) == target do
				left
			else
				-1
			end
		end
	end

	# isHappy
	# 编写一个算法来判断一个数 n 是不是快乐数。
	# 「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1
	# 也可能是 无限循环 但始终变不到 1。如果 可以变为  1，那么这个数就是快乐数。
	def isHappy(n) do
		nums = [4,16,37,58,89,145,42,20]
		fun = fn n,fun ->
			dup =
				"#{n}" |> String.split("") |> Enum.filter(fn item -> item != "" end) |> Enum.map(fn item -> String.to_integer(item) |> Letcodir.API.pow(2) end) |> Enum.sum
			if dup == 1 do
				true
			else
				if Enum.find(nums,fn item -> item==dup end) == nil do
					fun.(dup,fun)
				else
					false
				end
			end
		end
		fun.(n,fun)
	end

	# mergeTwoLists
	# 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
	def mergeTwoLists(l1,l2) when l1 == nil,do: l2
	def mergeTwoLists(l1,l2) when l2 == nil,do: l1
	def mergeTwoLists(l1,l2) do
		if l1.val < l2.val do
			%Letcodir.API.Node{val: l1.val,next: mergeTwoLists(l1.next,l2)}
		else
			%Letcodir.API.Node{val: l2.val,next: mergeTwoLists(l1,l2.next)}
		end
	end

	# isSymmetric
	# 给定一个二叉树，检查它是否是镜像对称的。
	# 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
	# 但是 [1,2,2,nil,3,nil,3] 则不是镜像对称的。
	def isSymmetric(root) when not is_nil(root),do: isSymmetric(root.left,root.right)
	defp isSymmetric(left, right) when is_nil(left) and is_nil(right),do: true
	defp isSymmetric(left, right) when is_nil(left) or is_nil(right),do: false
	defp isSymmetric(left, right) do
		if left.val != right.val do
			false
		else
			isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left)
		end
	end
end
